﻿//   1、二分查找
// （暴力解法）
// // class Solution {
// public:
//     int search(vector<int>& nums, int target) 
//     {
//         int i=0;
//         for(auto e:nums)
//         {
//             if(e==target)
//             {
//                 return i;
//             }
//             i++;        
//         }   
//         return -1;
//     }
// };
// 
// （二分解法）
//class Solution {
//public:
//    int search(vector<int>& nums, int target)
//    {
//        int left = 0, right = nums.size() - 1;
//        while (left <= right)
//        {
//            int mid = left + (right - left) / 2;  //防溢出
//            if (nums[mid] > target)
//            {
//                right = mid - 1;
//            }
//            else if (nums[mid] < target)
//            {
//                left = mid + 1;
//            }
//            else {
//                return mid;
//            }
//        }
//        return -1;
//    }
//};

//   2、在排序数组中查找元素的第⼀个和最后⼀个位置
//(暴力解法)
//public:
//    vector<int> searchRange(vector<int>& nums, int target)
//    {
//        int n = nums.size();
//        for (int i = 0; i < n; i++)
//        {
//            if (nums[i] == target)
//            {
//                for (int j = i; j < n; j++)
//                {
//                    if (nums[j] > target) return { i,j - 1 };
//                    else if (nums[n - 1] == target) return { i,n - 1 };
//                }
//            }
//        }
//        return{ -1,-1 };
//    }
//};

//（二分解法）

//class Solution
//{
//public:
//	vector<int> searchRange(vector<int>& nums, int target)
//	{
//		// 处理边界情况
//		if (nums.size() == 0) return { -1, -1 };
//		int begin = 0;
//		// 1. ⼆分左端点
//		int left = 0, right = nums.size() - 1;
//		while (left < right)
//		{
//			int mid = left + (right - left) / 2;
//			if (nums[mid] < target) left = mid + 1;
//			else right = mid;
//		}
//		// 判断是否有结果
//		if (nums[left] != target) return { -1, -1 };
//		else begin = left; // 标记⼀下左端点
//		// 2. ⼆分右端点
//		left = 0, right = nums.size() - 1;
//		while (left < right)
//		{
//			int mid = left + (right - left + 1) / 2;
//			if (nums[mid] <= target) left = mid;
//			else right = mid - 1;
//		}
//		return { begin, right };
//	}
//};


//3、x 的平方根 
//（暴力解法）
//class Solution {
//public:
//    int mySqrt(int x)
//    {
//        if (x < 1) return 0;
//        long long i = 0;
//        for (i = 0; i <= x; i++)
//        {
//            if (i * i == x) return i;
//            if (i * i > x) return i - 1;
//        }
//        return -1;
//    }
//};

//（2）二分查找

//class Solution {
//public:
//    int mySqrt(int x)
//    {
//        if (x < 1) return 0;
//        int left = 1, right = x;
//        while (right > left)
//        {
//            long long mid = left + (right - left + 1) / 2;
//            if (mid * mid > x) right = mid - 1;
//            else left = mid;
//        }
//        return left;
//    }
//};

//   4、搜索插入位置
//（1）暴力求解
//class Solution {
//public:
//    int searchInsert(vector<int>& nums, int target)
//    {
//        if (target <= nums[0]) return 0;
//        if (target > nums.back()) return nums.size();
//        if (target == nums.back()) return nums.size() - 1;
//        for (int i = 0; i < nums.size() - 1; i++)
//        {
//            if (nums[i] == target) return i;
//            if (nums[i]<target && nums[i + 1]>target) return i + 1;
//        }
//        return 0;
//    }
//};

//（2）二分算法
//class Solution {
//public:
//    int searchInsert(vector<int>& nums, int target)
//    {
//        int left = 0, right = nums.size() - 1;
//        while (right > left)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target) left = mid + 1;
//            else right = mid;
//        }
//        if (nums[left] < target) return right + 1;
//        return right;
//    }
//};